/*
 * Copyright (C) 2017 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.graph;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static java.util.Objects.requireNonNull;

import com.google.common.annotations.Beta;
import com.google.common.collect.AbstractIterator;
import com.google.common.collect.ImmutableSet;
import com.google.errorprone.annotations.DoNotMock;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import javax.annotation.CheckForNull;

/**
 * An object that can traverse the nodes that are reachable from a specified (set of) start node(s)
 * using a specified {@link SuccessorsFunction}.
 *
 * <p>There are two entry points for creating a {@code Traverser}: {@link
 * #forTree(SuccessorsFunction)} and {@link #forGraph(SuccessorsFunction)}. You should choose one
 * based on your answers to the following questions:
 *
 * <ol>
 *   <li>Is there only one path to any node that's reachable from any start node? (If so, the graph
 *       to be traversed is a tree or forest even if it is a subgraph of a graph which is neither.)
 *   <li>Are the node objects' implementations of {@code equals()}/{@code hashCode()} <a
 *       href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursive</a>?
 * </ol>
 *
 * <p>If your answers are:
 *
 * <ul>
 *   <li>(1) "no" and (2) "no", use {@link #forGraph(SuccessorsFunction)}.
 *   <li>(1) "yes" and (2) "yes", use {@link #forTree(SuccessorsFunction)}.
 *   <li>(1) "yes" and (2) "no", you can use either, but {@code forTree()} will be more efficient.
 *   <li>(1) "no" and (2) "yes", <b><i>neither will work</i></b>, but if you transform your node
 *       objects into a non-recursive form, you can use {@code forGraph()}.
 * </ul>
 *
 * @param <N> Node parameter type
 * @author Jens Nyman
 * @since 23.1
 */
@Beta
@DoNotMock(
        "Call forGraph or forTree, passing a lambda or a Graph with the desired edges (built with"
                + " GraphBuilder)")
@ElementTypesAreNonnullByDefault
public abstract class Traverser<N>
{
    private final SuccessorsFunction<N> successorFunction;

    private Traverser(SuccessorsFunction<N> successorFunction)
    {
        this.successorFunction = checkNotNull(successorFunction);
    }

    /**
     * Creates a new traverser for the given general {@code graph}.
     *
     * <p>Traversers created using this method are guaranteed to visit each node reachable from the
     * start node(s) at most once.
     *
     * <p>If you know that no node in {@code graph} is reachable by more than one path from the start
     * node(s), consider using {@link #forTree(SuccessorsFunction)} instead.
     *
     * <p><b>Performance notes</b>
     *
     * <ul>
     *   <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
     *       the start node), assuming that the node objects have <i>O(1)</i> {@code equals()} and
     *       {@code hashCode()} implementations. (See the <a
     *       href="https://github.com/google/guava/wiki/GraphsExplained#elements-must-be-useable-as-map-keys">
     *       notes on element objects</a> for more information.)
     *   <li>While traversing, the traverser will use <i>O(n)</i> space (where <i>n</i> is the number
     *       of nodes that have thus far been visited), plus <i>O(H)</i> space (where <i>H</i> is the
     *       number of nodes that have been seen but not yet visited, that is, the "horizon").
     * </ul>
     *
     * @param graph {@link SuccessorsFunction} representing a general graph that may have cycles.
     */
    public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph)
    {
        return new Traverser<N>(graph)
        {
            @Override
            Traversal<N> newTraversal()
            {
                return Traversal.inGraph(graph);
            }
        };
    }

    /**
     * Creates a new traverser for a directed acyclic graph that has at most one path from the start
     * node(s) to any node reachable from the start node(s), and has no paths from any start node to
     * any other start node, such as a tree or forest.
     *
     * <p>{@code forTree()} is especially useful (versus {@code forGraph()}) in cases where the data
     * structure being traversed is, in addition to being a tree/forest, also defined <a
     * href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursively</a>.
     * This is because the {@code forTree()}-based implementations don't keep track of visited nodes,
     * and therefore don't need to call `equals()` or `hashCode()` on the node objects; this saves
     * both time and space versus traversing the same graph using {@code forGraph()}.
     *
     * <p>Providing a graph to be traversed for which there is more than one path from the start
     * node(s) to any node may lead to:
     *
     * <ul>
     *   <li>Traversal not terminating (if the graph has cycles)
     *   <li>Nodes being visited multiple times (if multiple paths exist from any start node to any
     *       node reachable from any start node)
     * </ul>
     *
     * <p><b>Performance notes</b>
     *
     * <ul>
     *   <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
     *       the start node).
     *   <li>While traversing, the traverser will use <i>O(H)</i> space (where <i>H</i> is the number
     *       of nodes that have been seen but not yet visited, that is, the "horizon").
     * </ul>
     *
     * <p><b>Examples</b> (all edges are directed facing downwards)
     *
     * <p>The graph below would be valid input with start nodes of {@code a, f, c}. However, if {@code
     * b} were <i>also</i> a start node, then there would be multiple paths to reach {@code e} and
     * {@code h}.
     *
     * <pre>{@code
     *    a     b      c
     *   / \   / \     |
     *  /   \ /   \    |
     * d     e     f   g
     *       |
     *       |
     *       h
     * }</pre>
     *
     * <p>.
     *
     * <p>The graph below would be a valid input with start nodes of {@code a, f}. However, if {@code
     * b} were a start node, there would be multiple paths to {@code f}.
     *
     * <pre>{@code
     *    a     b
     *   / \   / \
     *  /   \ /   \
     * c     d     e
     *        \   /
     *         \ /
     *          f
     * }</pre>
     *
     * <p><b>Note on binary trees</b>
     *
     * <p>This method can be used to traverse over a binary tree. Given methods {@code
     * leftChild(node)} and {@code rightChild(node)}, this method can be called as
     *
     * <pre>{@code
     * Traverser.forTree(node -> ImmutableList.of(leftChild(node), rightChild(node)));
     * }</pre>
     *
     * @param tree {@link SuccessorsFunction} representing a directed acyclic graph that has at most
     *             one path between any two nodes
     */
    public static <N> Traverser<N> forTree(SuccessorsFunction<N> tree)
    {
        if (tree instanceof BaseGraph)
        {
            checkArgument(((BaseGraph<?>) tree).isDirected(), "Undirected graphs can never be trees.");
        }
        if (tree instanceof Network)
        {
            checkArgument(((Network<?, ?>) tree).isDirected(), "Undirected networks can never be trees.");
        }
        return new Traverser<N>(tree)
        {
            @Override
            Traversal<N> newTraversal()
            {
                return Traversal.inTree(tree);
            }
        };
    }

    /**
     * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
     * the order of a breadth-first traversal. That is, all the nodes of depth 0 are returned, then
     * depth 1, then 2, and so on.
     *
     * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
     * the order {@code abcdef} (assuming successors are returned in alphabetical order).
     *
     * <pre>{@code
     * b ---- a ---- d
     * |      |
     * |      |
     * e ---- c ---- f
     * }</pre>
     *
     * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
     * while iteration is in progress.
     *
     * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
     * compute its next element on the fly. It is thus possible to limit the traversal to a certain
     * number of nodes as follows:
     *
     * <pre>{@code
     * Iterables.limit(Traverser.forGraph(graph).breadthFirst(node), maxNumberOfNodes);
     * }</pre>
     *
     * <p>See <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Wikipedia</a> for more
     * info.
     *
     * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
     */
    public final Iterable<N> breadthFirst(N startNode)
    {
        return breadthFirst(ImmutableSet.of(startNode));
    }

    /**
     * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
     * startNodes}, in the order of a breadth-first traversal. This is equivalent to a breadth-first
     * traversal of a graph with an additional root node whose successors are the listed {@code
     * startNodes}.
     *
     * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
     * @see #breadthFirst(Object)
     * @since 24.1
     */
    public final Iterable<N> breadthFirst(Iterable<? extends N> startNodes)
    {
        ImmutableSet<N> validated = validate(startNodes);
        return new Iterable<N>()
        {
            @Override
            public Iterator<N> iterator()
            {
                return newTraversal().breadthFirst(validated.iterator());
            }
        };
    }

    /**
     * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
     * the order of a depth-first pre-order traversal. "Pre-order" implies that nodes appear in the
     * {@code Iterable} in the order in which they are first visited.
     *
     * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
     * the order {@code abecfd} (assuming successors are returned in alphabetical order).
     *
     * <pre>{@code
     * b ---- a ---- d
     * |      |
     * |      |
     * e ---- c ---- f
     * }</pre>
     *
     * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
     * while iteration is in progress.
     *
     * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
     * compute its next element on the fly. It is thus possible to limit the traversal to a certain
     * number of nodes as follows:
     *
     * <pre>{@code
     * Iterables.limit(
     *     Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes);
     * }</pre>
     *
     * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
     *
     * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
     */
    public final Iterable<N> depthFirstPreOrder(N startNode)
    {
        return depthFirstPreOrder(ImmutableSet.of(startNode));
    }

    /**
     * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
     * startNodes}, in the order of a depth-first pre-order traversal. This is equivalent to a
     * depth-first pre-order traversal of a graph with an additional root node whose successors are
     * the listed {@code startNodes}.
     *
     * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
     * @see #depthFirstPreOrder(Object)
     * @since 24.1
     */
    public final Iterable<N> depthFirstPreOrder(Iterable<? extends N> startNodes)
    {
        ImmutableSet<N> validated = validate(startNodes);
        return new Iterable<N>()
        {
            @Override
            public Iterator<N> iterator()
            {
                return newTraversal().preOrder(validated.iterator());
            }
        };
    }

    /**
     * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
     * the order of a depth-first post-order traversal. "Post-order" implies that nodes appear in the
     * {@code Iterable} in the order in which they are visited for the last time.
     *
     * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
     * the order {@code fcebda} (assuming successors are returned in alphabetical order).
     *
     * <pre>{@code
     * b ---- a ---- d
     * |      |
     * |      |
     * e ---- c ---- f
     * }</pre>
     *
     * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
     * while iteration is in progress.
     *
     * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
     * compute its next element on the fly. It is thus possible to limit the traversal to a certain
     * number of nodes as follows:
     *
     * <pre>{@code
     * Iterables.limit(
     *     Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes);
     * }</pre>
     *
     * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
     *
     * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
     */
    public final Iterable<N> depthFirstPostOrder(N startNode)
    {
        return depthFirstPostOrder(ImmutableSet.of(startNode));
    }

    /**
     * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
     * startNodes}, in the order of a depth-first post-order traversal. This is equivalent to a
     * depth-first post-order traversal of a graph with an additional root node whose successors are
     * the listed {@code startNodes}.
     *
     * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
     * @see #depthFirstPostOrder(Object)
     * @since 24.1
     */
    public final Iterable<N> depthFirstPostOrder(Iterable<? extends N> startNodes)
    {
        ImmutableSet<N> validated = validate(startNodes);
        return new Iterable<N>()
        {
            @Override
            public Iterator<N> iterator()
            {
                return newTraversal().postOrder(validated.iterator());
            }
        };
    }

    abstract Traversal<N> newTraversal();

    @SuppressWarnings("CheckReturnValue")
    private ImmutableSet<N> validate(Iterable<? extends N> startNodes)
    {
        ImmutableSet<N> copy = ImmutableSet.copyOf(startNodes);
        for (N node : copy)
        {
            successorFunction.successors(node); // Will throw if node doesn't exist
        }
        return copy;
    }

    /**
     * Abstracts away the difference between traversing a graph vs. a tree. For a tree, we just take
     * the next element from the next non-empty iterator; for graph, we need to loop through the next
     * non-empty iterator to find first unvisited node.
     */
    private abstract static class Traversal<N>
    {
        final SuccessorsFunction<N> successorFunction;

        Traversal(SuccessorsFunction<N> successorFunction)
        {
            this.successorFunction = successorFunction;
        }

        static <N> Traversal<N> inGraph(SuccessorsFunction<N> graph)
        {
            Set<N> visited = new HashSet<>();
            return new Traversal<N>(graph)
            {
                @Override
                @CheckForNull
                N visitNext(Deque<Iterator<? extends N>> horizon)
                {
                    Iterator<? extends N> top = horizon.getFirst();
                    while (top.hasNext())
                    {
                        N element = top.next();
                        // requireNonNull is safe because horizon contains only graph nodes.
                        /*
                         * TODO(cpovirk): Replace these two statements with one (`N element =
                         * requireNonNull(top.next())`) once our checker supports it.
                         *
                         * (The problem is likely
                         * https://github.com/jspecify/nullness-checker-for-checker-framework/blob/61aafa4ae52594830cfc2d61c8b113009dbdb045/src/main/java/com/google/jspecify/nullness/NullSpecAnnotatedTypeFactory.java#L896)
                         */
                        requireNonNull(element);
                        if (visited.add(element))
                        {
                            return element;
                        }
                    }
                    horizon.removeFirst();
                    return null;
                }
            };
        }

        static <N> Traversal<N> inTree(SuccessorsFunction<N> tree)
        {
            return new Traversal<N>(tree)
            {
                @CheckForNull
                @Override
                N visitNext(Deque<Iterator<? extends N>> horizon)
                {
                    Iterator<? extends N> top = horizon.getFirst();
                    if (top.hasNext())
                    {
                        return checkNotNull(top.next());
                    }
                    horizon.removeFirst();
                    return null;
                }
            };
        }

        final Iterator<N> breadthFirst(Iterator<? extends N> startNodes)
        {
            return topDown(startNodes, InsertionOrder.BACK);
        }

        final Iterator<N> preOrder(Iterator<? extends N> startNodes)
        {
            return topDown(startNodes, InsertionOrder.FRONT);
        }

        /**
         * In top-down traversal, an ancestor node is always traversed before any of its descendant
         * nodes. The traversal order among descendant nodes (particularly aunts and nieces) are
         * determined by the {@code InsertionOrder} parameter: nieces are placed at the FRONT before
         * aunts for pre-order; while in BFS they are placed at the BACK after aunts.
         */
        private Iterator<N> topDown(Iterator<? extends N> startNodes, InsertionOrder order)
        {
            Deque<Iterator<? extends N>> horizon = new ArrayDeque<>();
            horizon.add(startNodes);
            return new AbstractIterator<N>()
            {
                @Override
                @CheckForNull
                protected N computeNext()
                {
                    do
                    {
                        N next = visitNext(horizon);
                        if (next != null)
                        {
                            Iterator<? extends N> successors = successorFunction.successors(next).iterator();
                            if (successors.hasNext())
                            {
                                // BFS: horizon.addLast(successors)
                                // Pre-order: horizon.addFirst(successors)
                                order.insertInto(horizon, successors);
                            }
                            return next;
                        }
                    }
                    while (!horizon.isEmpty());
                    return endOfData();
                }
            };
        }

        final Iterator<N> postOrder(Iterator<? extends N> startNodes)
        {
            Deque<N> ancestorStack = new ArrayDeque<>();
            Deque<Iterator<? extends N>> horizon = new ArrayDeque<>();
            horizon.add(startNodes);
            return new AbstractIterator<N>()
            {
                @Override
                @CheckForNull
                protected N computeNext()
                {
                    for (N next = visitNext(horizon); next != null; next = visitNext(horizon))
                    {
                        Iterator<? extends N> successors = successorFunction.successors(next).iterator();
                        if (!successors.hasNext())
                        {
                            return next;
                        }
                        horizon.addFirst(successors);
                        ancestorStack.push(next);
                    }
                    // TODO(b/192579700): Use a ternary once it no longer confuses our nullness checker.
                    if (!ancestorStack.isEmpty())
                    {
                        return ancestorStack.pop();
                    }
                    return endOfData();
                }
            };
        }

        /**
         * Visits the next node from the top iterator of {@code horizon} and returns the visited node.
         * Null is returned to indicate reaching the end of the top iterator.
         *
         * <p>For example, if horizon is {@code [[a, b], [c, d], [e]]}, {@code visitNext()} will return
         * {@code [a, b, null, c, d, null, e, null]} sequentially, encoding the topological structure.
         * (Note, however, that the callers of {@code visitNext()} often insert additional iterators
         * into {@code horizon} between calls to {@code visitNext()}. This causes them to receive
         * additional values interleaved with those shown above.)
         */
        @CheckForNull
        abstract N visitNext(Deque<Iterator<? extends N>> horizon);
    }

    /**
     * Poor man's method reference for {@code Deque::addFirst} and {@code Deque::addLast}.
     */
    private enum InsertionOrder
    {
        FRONT
                {
                    @Override
                    <T> void insertInto(Deque<T> deque, T value)
                    {
                        deque.addFirst(value);
                    }
                },
        BACK
                {
                    @Override
                    <T> void insertInto(Deque<T> deque, T value)
                    {
                        deque.addLast(value);
                    }
                };

        abstract <T> void insertInto(Deque<T> deque, T value);
    }
}
